// 2010年版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package token

import (
	"fmt"
	"sort"
	"sync"
)

// -----------------------------------------------------------------------------
// 位置

// 位置描述任意源位置
// 包括文件、行和列位置。
// 如果行号大于0，则位置有效。
// None
type Position struct {
	Filename string // 文件名（如果有）
	Offset   int    // 偏移量，从0开始
	Line     int    // 行号，从1开始
	Column   int    // 列编号，从1开始（字节计数）
}

// IsValid报告职位是否有效。
func (pos *Position) IsValid() bool { return pos.Line > 0 }

// String以以下几种形式之一返回字符串：
// None
// 文件：行：具有文件名的列有效位置
// 文件：具有文件名但没有列的行有效位置（列==0）
// 行：不带文件名的列的有效位置
// 行有效位置，无文件名，无列（列==0）
// 文件名为的文件位置无效
// -没有文件名的位置无效
// None
func (pos Position) String() string {
	s := pos.Filename
	if pos.IsValid() {
		if s != "" {
			s += ":"
		}
		s += fmt.Sprintf("%d", pos.Line)
		if pos.Column != 0 {
			s += fmt.Sprintf(":%d", pos.Column)
		}
	}
	if s == "" {
		s = "-"
	}
	return s
}

// Pos是文件集中源位置的压缩编码。
// 它可以转换为一个更方便的位置，但更多
// 更大的代表性。
// None
// 给定文件的Pos值是[base，base+size]范围内的数字，
// 其中，在将文件添加到文件集中时指定了基准和大小。
// Pos值与相应文件基之间的差异
// 对应于该位置的字节偏移量（由Pos值表示）
// 从文件的开头开始。因此，文件基偏移量是Pos值
// 表示文件中的第一个字节。
// None
// 要为特定源偏移量（以字节为单位）创建Pos值，
// 首先使用FileSet.AddFile将相应的文件添加到当前文件集中
// 然后为该文件调用File.Pos（offset）。给定一个Pos值p
// 对于特定的文件集fset，相应的位置值为
// 通过调用fset.Position（p）获得。
// None
// Pos值可以直接与常用的比较运算符进行比较：
// 如果两个Pos值p和q在同一个文件中，则比较p和q是正确的
// 相当于比较各个源文件偏移量。如果p和q
// 在不同的文件中，如果添加了p所暗示的文件，则p<q为真
// 到q所暗示的文件之前的相应文件集。
// None
type Pos int

// Pos的零值为NoPos；没有文件和行信息
// 并且NoPos.IsValid（）为false。诺波斯总是
// 小于任何其他Pos值。对应的位置值
// 对于NoPos，是位置的零值。
// None
const NoPos Pos = 0

// IsValid报告职位是否有效。
func (p Pos) IsValid() bool {
	return p != NoPos
}

// -----------------------------------------------------------------------------
// 文件

// 文件是属于文件集的文件的句柄。
// 文件具有名称、大小和行偏移量表。
// None
type File struct {
	set  *FileSet
	name string // 提供给AddFile的文件名
	base int    // 此文件的Pos值范围为[base…base+size]
	size int    // 提供给AddFile的文件大小

	// 线路和信息由互斥锁保护
	mutex sync.Mutex
	lines []int // 行包含每行第一个字符的偏移量（第一个条目始终为0）
	infos []lineInfo
}

// Name返回在AddFile中注册的文件f的文件名。
func (f *File) Name() string {
	return f.name
}

// Base返回在AddFile中注册的文件f的基偏移量。
func (f *File) Base() int {
	return f.base
}

// Size返回在AddFile中注册的文件f的大小。
func (f *File) Size() int {
	return f.size
}

// LineCount返回文件f中的行数。
func (f *File) LineCount() int {
	f.mutex.Lock()
	n := len(f.lines)
	f.mutex.Unlock()
	return n
}

// AddLine为新线添加线偏移。
// 行偏移必须大于上一行的偏移
// 并且小于文件大小；否则，将忽略线偏移。
// None
func (f *File) AddLine(offset int) {
	f.mutex.Lock()
	if i := len(f.lines); (i == 0 || f.lines[i-1] < offset) && offset < f.size {
		f.lines = append(f.lines, offset)
	}
	f.mutex.Unlock()
}

// MergeLine将一行与下一行合并。它类似于替换
// 行尾的换行符，带有空格（不更改
// 剩余偏移量）。要获得线路编号，请参考例如Position.line。
// 如果给定的行号无效，MergeLine将死机。
// None
func (f *File) MergeLine(line int) {
	if line < 1 {
		panic(fmt.Sprintf("invalid line number %d (should be >= 1)", line))
	}
	f.mutex.Lock()
	defer f.mutex.Unlock()
	if line >= len(f.lines) {
		panic(fmt.Sprintf("invalid line number %d (should be < %d)", line, len(f.lines)))
	}
	// 要将编号为<line>的行与编号为<line+1>的行合并，
	// 我们需要删除与该行对应的行中的条目
	// 编号<line+1>。与该行对应的行中的条目
	// 编号的<line+1>位于索引<line>，因为索引位于行中
	// 以0为基础，行号以1为基础。
	copy(f.lines[line:], f.lines[line+1:])
	f.lines = f.lines[:len(f.lines)-1]
}

// SetLines设置文件的行偏移量并报告是否成功。
// 行偏移是每行的第一个字符的偏移；
// 例如，对于内容“ab\nc\n”，行偏移量为{0,3}。
// 空文件的行偏移量表为空。
// 每行偏移量必须大于上一行的偏移量
// 并且小于文件大小；否则，设置行将失败并返回
// 错误的
// 调用方不能在SetLines返回后改变提供的切片。
// None
func (f *File) SetLines(lines []int) bool {
	// 验证行表的有效性
	size := f.size
	for i, offset := range lines {
		if i > 0 && offset <= lines[i-1] || size <= offset {
			return false
		}
	}

	// 设置行表
	f.mutex.Lock()
	f.lines = lines
	f.mutex.Unlock()
	return true
}

// SetLinesForContent设置给定文件内容的行偏移量。
// 它忽略了位置改变
func (f *File) SetLinesForContent(content []byte) {
	var lines []int
	line := 0
	for offset, b := range content {
		if line >= 0 {
			lines = append(lines, line)
		}
		line = -1
		if b == '\n' {
			line = offset + 1
		}
	}

	// 设置行表
	f.mutex.Lock()
	f.lines = lines
	f.mutex.Unlock()
}

// LineStart返回指定行起点的位置值。
// 它忽略使用AddLineColumnInfo设置的任何备选位置。
// 如果基于1的行号无效，LineStart将出现恐慌。
func (f *File) LineStart(line int) Pos {
	if line < 1 {
		panic(fmt.Sprintf("invalid line number %d (should be >= 1)", line))
	}
	f.mutex.Lock()
	defer f.mutex.Unlock()
	if line > len(f.lines) {
		panic(fmt.Sprintf("invalid line number %d (should be < %d)", line, len(f.lines)))
	}
	return Pos(f.base + f.lines[line-1])
}

// lineInfo对象描述替代文件、行和列
// 编号信息（如通过
// 对于给定的文件偏移量。
type lineInfo struct {
	// 字段被导出以使其可供gob访问
	Offset       int
	Filename     string
	Line, Column int
}

// AddLineInfo类似于AddLineColumnInfo，有一个column=1参数。
// 这是为了在Go 1.11之前向后兼容代码。
// None
func (f *File) AddLineInfo(offset int, filename string, line int) {
	f.AddLineColumnInfo(offset, filename, line, 1)
}

// AddLineColumnInfo添加可选文件、行和列号
// 给定文件偏移量的信息。偏移量必须更大
// 大于先前添加的替代行信息的偏移量
// 并且小于文件大小；否则，信息将被删除
// 忽略。
// None
// AddLineColumnInfo通常用于注册替代位置
// 行指令的信息，例如
// None
func (f *File) AddLineColumnInfo(offset int, filename string, line, column int) {
	f.mutex.Lock()
	if i := len(f.infos); i == 0 || f.infos[i-1].Offset < offset && offset < f.size {
		f.infos = append(f.infos, lineInfo{offset, filename, line, column})
	}
	f.mutex.Unlock()
}

// Pos返回给定文件偏移量的Pos值；
// 偏移量必须小于等于f.Size（）。
// f、 位置（f.偏移量（p））==p。
// None
func (f *File) Pos(offset int) Pos {
	if offset > f.size {
		panic(fmt.Sprintf("invalid file offset %d (should be <= %d)", offset, f.size))
	}
	return Pos(f.base + offset)
}

// Offset返回给定文件位置p的偏移量；
// p必须是该文件中的有效Pos值。
// f、 偏移量（f.Pos（偏移量））==偏移量。
// None
func (f *File) Offset(p Pos) int {
	if int(p) < f.base || int(p) > f.base+f.size {
		panic(fmt.Sprintf("invalid Pos value %d (should be in [%d, %d])", p, f.base, f.base+f.size))
	}
	return int(p) - f.base
}

// Line返回给定文件位置p的行号；
// p必须是该文件或NoPos中的Pos值。
// None
func (f *File) Line(p Pos) int {
	return f.Position(p).Line
}

func searchLineInfos(a []lineInfo, x int) int {
	return sort.Search(len(a), func(i int) bool { return a[i].Offset > x }) - 1
}

// 解包返回文件偏移量的文件名、行号和列号。
// 如果设置了adjusted，unpack将返回文件名和行信息
// 可能由
// None
func (f *File) unpack(offset int, adjusted bool) (filename string, line, column int) {
	f.mutex.Lock()
	defer f.mutex.Unlock()
	filename = f.name
	if i := searchInts(f.lines, offset); i >= 0 {
		line, column = i+1, offset-f.lines[i]+1
	}
	if adjusted && len(f.infos) > 0 {
		// 很少有文件有额外的行信息
		if i := searchLineInfos(f.infos, offset); i >= 0 {
			alt := &f.infos[i]
			filename = alt.Filename
			if i := searchInts(f.lines, alt.Offset); i >= 0 {
				// i+1是记录备选位置的行
				d := line - (i + 1) // 距备用位置基准的线距离
				line = alt.Line + d
				if alt.Column == 0 {
					// 可选列未知=>相对列未知
					// （行指令的当前规范要求
					// 这将一直应用到下一个PosBase/line指令，
					// 不只是在新的换行之前）
					column = 0
				} else if d == 0 {
					// 备用位置基础位于当前行上
					// =>列是相对于可选列的
					column = alt.Column + (offset - alt.Offset)
				}
			}
		}
	}
	return
}

func (f *File) position(p Pos, adjusted bool) (pos Position) {
	offset := int(p) - f.base
	pos.Offset = offset
	pos.Filename, pos.Line, pos.Column = f.unpack(offset, adjusted)
	return
}

// PositionFor返回给定文件位置p的位置值。
// 如果设置了“调整”，则可以通过改变位置来调整位置
// None
// p必须是f或NoPos中的Pos值。
// None
func (f *File) PositionFor(p Pos, adjusted bool) (pos Position) {
	if p != NoPos {
		if int(p) < f.base || int(p) > f.base+f.size {
			panic(fmt.Sprintf("invalid Pos value %d (should be in [%d, %d])", p, f.base, f.base+f.size))
		}
		pos = f.position(p, adjusted)
	}
	return
}

// Position返回给定文件位置p的位置值。
// 调用f.Position（p）等同于调用f.PositionFor（p，true）。
// None
func (f *File) Position(p Pos) (pos Position) {
	return f.PositionFor(p, true)
}

// -----------------------------------------------------------------------------
// 文件集

// 文件集表示一组源文件。
// 同步文件集的方法；多重goroutine
// 可以同时调用它们。
// None
// 文件集中每个文件的字节偏移量映射到
// 不同（整数）间隔，一个间隔[基数，基数+大小]
// 每个文件。Base表示文件中的第一个字节和大小
// 是相应的文件大小。Pos值是这样的值
// 间歇。通过确定Pos值所属的间隔
// 到、文件、其文件基以及字节偏移量（位置）
// 可以计算所表示的Pos值。
// None
// 添加新文件时，必须提供文件库。那可以
// 是超过任意时间间隔末尾的任意整数值
// 文件已在文件集中。为了方便起见，FileSet.Base提供了
// 这样一个值，它只是most的Pos间隔的结束
// 最近添加的文件，加上一个。除非有必要延长合同期限
// 间隔之后，应使用FileSet.Base作为参数
// 对于FileSet.AddFile。
// None
type FileSet struct {
	mutex sync.RWMutex // 保护文件集
	base  int          // 下一个文件的基准偏移量
	files []*File      // 按添加到集合的顺序排列的文件列表
	last  *File        // 上次查找的文件的缓存
}

// 新建文件集创建一个新的文件集。
func NewFileSet() *FileSet {
	return &FileSet{
		base: 1, // 0==NoPos
	}
}

// Base返回必须提供给的最小基偏移量
// 添加下一个文件时添加文件。
// None
func (s *FileSet) Base() int {
	s.mutex.RLock()
	b := s.base
	s.mutex.RUnlock()
	return b

}

// AddFile使用给定的文件名、基偏移量和文件大小添加新文件
// 返回到文件集并返回该文件。多个文件可能具有相同的属性
// 名称基偏移量不得小于文件集的base（），并且
// 大小不能为负数。作为特殊情况，如果提供负基极，
// 而是使用文件集的Base（）的当前值。
// None
// 添加文件会将文件集的Base（）值设置为Base+size+1
// 作为下一个文件的最小基值。以下关系
// 存在于给定文件偏移量的Pos值p之间：
// None
// int（p）=基准+基准
// None
// offs在[0，size]范围内，因此p在[base，base+size]范围内。
// 为方便起见，可以使用File.Pos创建文件特定位置
// 来自文件偏移量的值。
// None
func (s *FileSet) AddFile(filename string, base, size int) *File {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	if base < 0 {
		base = s.base
	}
	if base < s.base {
		panic(fmt.Sprintf("invalid base %d (should be >= %d)", base, s.base))
	}
	if size < 0 {
		panic(fmt.Sprintf("invalid size %d (should be >= 0)", size))
	}
	// 基本值>=s。基本值和大小>=0
	f := &File{set: s, name: filename, base: base, size: size, lines: []int{0}}
	base += size + 1 // +1因为EOF也有一个位置
	if base < 0 {
		panic("token.Pos offset overflow (> 2G of source code in file set)")
	}
	// 将文件添加到文件集
	s.base = base
	s.files = append(s.files, f)
	s.last = f
	return f
}

// 按添加顺序对文件集中的文件迭代调用f
// 直到f返回false。
// None
func (s *FileSet) Iterate(f func(*File) bool) {
	for i := 0; ; i++ {
		var file *File
		s.mutex.RLock()
		if i < len(s.files) {
			file = s.files[i]
		}
		s.mutex.RUnlock()
		if file == nil || !f(file) {
			break
		}
	}
}

func searchFiles(a []*File, x int) int {
	return sort.Search(len(a), func(i int) bool { return a[i].base > x }) - 1
}

func (s *FileSet) file(p Pos) *File {
	s.mutex.RLock()
	// 常见情况：p位于最后一个文件中
	if f := s.last; f != nil && f.base <= int(p) && int(p) <= f.base+f.size {
		s.mutex.RUnlock()
		return f
	}
	// p不在最后一个文件中-搜索所有文件
	if i := searchFiles(s.files, int(p)); i >= 0 {
		f := s.files[i]
		// f、 根据搜索文件的定义，base<=int（p）
		if int(p) <= f.base+f.size {
			s.mutex.RUnlock()
			s.mutex.Lock()
			s.last = f // 比赛正常-s.last只是一个缓存
			s.mutex.Unlock()
			return f
		}
	}
	s.mutex.RUnlock()
	return nil
}

// File返回包含位置p的文件。
// 如果找不到这样的文件（例如p==NoPos），
// 结果是零。
// None
func (s *FileSet) File(p Pos) (f *File) {
	if p != NoPos {
		f = s.file(p)
	}
	return
}

// PositionFor将文件集中的Pos p转换为位置值。
// 如果设置了“调整”，则可以通过改变位置来调整位置
// None
// p必须是s或NoPos中的Pos值。
// None
func (s *FileSet) PositionFor(p Pos, adjusted bool) (pos Position) {
	if p != NoPos {
		if f := s.file(p); f != nil {
			return f.position(p, adjusted)
		}
	}
	return
}

// Position将文件集中的Pos p转换为Position值。
// 调用s.Position（p）等同于调用s.PositionFor（p，true）。
// None
func (s *FileSet) Position(p Pos) (pos Position) {
	return s.PositionFor(p, true)
}

// -----------------------------------------------------------------------------
// 辅助函数

func searchInts(a []int, x int) int {
	// 此函数体是以下函数的手动内联版本：
	// None
	// 返回sort.Search（len（a），func（i int）bool{returna[i]>x}）-1
	// None
	// 有了更好的编译器优化，在
	// 未来，但目前这一变化改善了go/打印机
	// 基准性能下降约30%。这直接影响到
	// gofmt的速度，因此似乎是值得的（2011-04-29）。
	// TODO（gri）：当编译器赶上时删除此选项。
	i, j := 0, len(a)
	for i < j {
		h := i + (j-i)>>1 // 在计算h时避免溢出
		// 我≤ h<j
		if a[h] <= x {
			i = h + 1
		} else {
			j = h
		}
	}
	return i - 1
}
